ExeGPT: Constraint-Aware ResourceScheduling for LLM inference

作者信息 Hanyang University在ASPLOS 2024的一篇工作

链接：[2404.07947] ExeGPT: Constraint-Aware Resource Scheduling for LLM Inference

摘要：

This paper presents ExeGPT, a distributed system designed for constraint-aware LLM inference. ExeGPT finds and runs with an optimal execution schedule to maximize inference throughput while satisfying a given latency constraint【在满足latency的情况下最大化吞吐量】. By leveraging the distribution of input and output sequences, it effectively allocates resources and determines optimal execution configurations, including batch sizes and partial tensor parallelism【根据输入输出确定batch size和并行策略】. We also introduce two scheduling strategies based on Round-Robin Allocation and Workload-Aware Allocation policies, suitable for different NLP workloads【提出了两种调度策略】. We evaluate ExeGPT on six LLM instances of T5, OPT, and GPT-3 and five NLP tasks, each with four distinct latency constraints. Compared to FasterTransformer, ExeGPT achieves up to 15.2x improvements in throughput and 6x improvements in latency. Overall, ExeGPT achieves an average throughput gain of 2.9x across twenty evaluation scenarios. Moreover, when adapting to changing sequence distributions, the cost of adjusting the schedule in ExeGPT is reasonably modest. ExeGPT proves to be an effective solution for optimizing and executing LLM inference for diverse NLP workload and serving conditions.

Introduction

背景

LLM inference：

1. used in NLP tasks，就会有两个阶段，先encode，再decode。
2. 对于Transformer-based models，encode和decode合一了，decoder-only models，其实就是prefill变成了encode。

蓝色是encode，橙色是decode

1. Faster Transformer（PP=2，TP=1）：decode2需要等待encode2完成，有很长的气泡。且在后面decode部分，可以发现随着时间增长，已完成的没有退出，batch size并没有减小，导致有很多白框（浪费的计算时间）。
2. DeepSpeed Inference同理，有很多小的白框
3. Orca采用了iteration-level的调度，解决了这个白框的问题。但仍然没有考虑encode和decode时间差异较大的问题，导致采用PP的情况下有很多气泡。并且，将decode和encode放在一起，更加导致了其完成时间的不稳定。

先前工作存在的问题

1. encode时间相比decode时间较长，采用iteration-level调度下decode过程时间不稳定，PP情况下可能会有很多气泡，会导致无法控制的延迟。
2. 目前系统的inefficient trade-off mechanism between throughput and latency。假如要增大latency限制，就会选择缩小batch size，就会间接导致throughput缩小。

难点

Design

to read（可能的不同）:

• 他们有无考虑优先级，insensitive是否会阻碍sensitive的推理
• 他们没有利用offload和cpu来处理序列的动态性
• 他们是encoder decoder分离的架构，我们是chunked prefill架构（chunked prefill节省模型空间的好处……）

我们的出发点：

• 维持latency sensitive请求的slo的情况下，maximize best effort请求的吞吐量（parallel mlp，cpu，main memory）
• 在同时处理latency sensitive和best effort请求的情况下，高性价比地降低best effort对latency sensitive请求推理的影响（best effort不应该影响latency sensitive的请求进入）
• 针对latency sensitive和best effort的动态性，实时调整调度策略（offload）。

ExeGPT：给定了一个latency constraint，实现推理的最大throughput。

架构设计

• XProfiler
  • 测量每层的attention kernel时间和其他函数的时间
  • 测量TP和PP同步的时间
• XSimulator
  • 根据scheduler提供并行策略和batch size，模拟出每个encoding和decoding的expected batch sizes
• XScheduler
  • 生成最优策略
• XRunner
  • 执行

ExeGPT工作中将调度策略分为了两类

• Round-Robin Allocation
• Workload-Aware Allocation
  • WAA-C：根据计算量分
  • WAA-M：根据占用内存分

• a：会因为encoding和decoding时间差异而产生很多气泡
• b：减少了很多气泡的生成，但是会因为batch太大而latency比较大
• c：将encoding的batch再次切分为几个micro-batch，从而减少了latency，但也减少了throughput
• d：将部分GPU设置为TP组合，从而减少了PP深度，也减少了latency，同时增加了吞吐量

但他这幅图，在图c中，加入1之后，假如需要decoding时间不变，是否需要减少2的batch大小才可能实现这里面没有气泡？感觉这里不是很make sense啊。。

然后，该工作采用了贝叶斯优化，在不超过Latency SLO的情况下最大化吞吐量。

然后，又因为这些变量对吞吐量的影响是单调的，该工作基于分支定界法（branch and bound）加速了计算。

取两个变量为例子。

1. 从Queue中取出一个block。
2. 判断左上和右下哪个吞吐量好，假如是左上吞吐量好，则将块分成左右两块；假如是右下吞吐量好，则将块分成是上下两块。
3. 分出来的两个块，假如左下不违反latency，则放入Queue中。
4. 减枝
   1. 比较分出来的两个块满足latency bound的右上值，假如Queue中存在某个block，其右上吞吐量小于该值，则将该block从Queue中逐出。

ExeGPT同时支持了动态调整encoder的batch size，使得负载更为均衡。

同时，SImulator通过之前的数据集的输入输出频率和相关性计算请求在该iteration完成decode的概率。

创新点

实验评估

Q&A